import java.util.Arrays;

public class Main {

    public static void quickSort(int[]array){
        quickSortRange(array,0,array.length-1);
    }
    private static void quickSortRange(int[]arr,int fromIdx,int toIdx){
        //计算递归的退出条件
        int size=toIdx-fromIdx+1;
        //当区间内元素小于或者只有一个时退出递归
        if(size<=1){
            return ;
        }
        int pivotIdx=parttion(arr,fromIdx,toIdx);
        quickSortRange(arr,fromIdx,pivotIdx-1);
        quickSortRange(arr,pivotIdx+1,toIdx);
    }
    //parttion的Hoare法
    private static int parttion(int[]array,int start,int end){
        int fromIdx=start;
        int toIdx=end;
        //pivot一般选最左边或者最右边
        int pivot=array[fromIdx];
        while(fromIdx<toIdx){
            //找右边小于pivot的
            while(fromIdx<toIdx&&pivot<=array[toIdx]){
                toIdx--;
            }
            //找左边大于pivot的
            while(fromIdx<toIdx&&pivot>=array[fromIdx]){
                fromIdx++;
            }
            //将找到的相互交换,让左侧小于pivot,让右侧大于pivot
            swap(array,fromIdx,toIdx);
        }
       //最后把pivot交换到中间，完成一次parttion
        swap(array,fromIdx,start);
        return fromIdx;
    }
    private static void swap(int[]arr,int i,int j){

        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }

    public static void main(String[] args) {
        int[]arr={1,7,4,5,1,0,-2,9,10};
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
